package day1.mycomparator;

import java.util.Comparator;
import java.util.PriorityQueue;

/**
 * @author pacai
 * @version 1.0
 */
public class MergeSortedLists {
    public static class ListNode {
        int val;
        ListNode next;
    }

    public static class ListNodeComparator implements Comparator<ListNode> {
        @Override
        public int compare(ListNode o1, ListNode o2) {
            return o1.val - o2.val;
        }
    }


    public static ListNode mergeKLists(ListNode[] lists) {
        if (lists == null) {
            return null;
        }

        PriorityQueue<ListNode> priorityQueue = new PriorityQueue<>();
        for (int i = 0; i < lists.length; i++) {
            if (lists[i] != null) {
                priorityQueue.add(lists[i]);//放入链表的头元素
            }
        }

        if (priorityQueue.isEmpty()) {
            return null;
        }

        ListNode head = priorityQueue.poll();
        ListNode pre = head;
        if (pre.next != null) {
            priorityQueue.add(pre.next);//根据优先级队列的特性，取出对应的有序元素
        }
        while (!priorityQueue.isEmpty()) {
            ListNode cur = priorityQueue.poll();
            pre.next = cur;
            pre = cur;
            if (cur.next != null) {
                priorityQueue.add(cur.next);//当有一条链表全部放入后，剩余链表的元素的next无需改动
            }
        }
        return head;
    }
}
